package com.ly.algorithm.leetcode.heap;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Classname Problem215
 * @Description
 *
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 示例 1:
 *
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * 示例 2:
 *
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 *
 *
 *
 * @Date 2020/12/19 19:22
 * @Author 冷心影翼
 */
public class Problem215 {

	public static void main(String[] args) {
		Solution215 solution215 = new Solution215();
		System.out.println(solution215.findKthLargestByHeap(new int[]{3,2,3,1,2,4,5,5,6}, 4));
	}
}


class Solution215 {
	public int findKthLargest(int[] nums, int k) {
		PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
		for(int i=0;i<nums.length;i++) {
			priorityQueue.add(nums[i]);
		}
		while (priorityQueue.size() > k) {
			priorityQueue.poll();
		}
		return priorityQueue.peek();
	}

	public int findKthLargestByHeap(int[] nums, int k) {
		buildHeap(nums);
		for(int i=nums.length-1;i>nums.length - k;i--) {
			delete(nums,i);
		}
		return nums[0];
	}

	public void delete(int[] nums,int n) {
		nums[0] = nums[n];
		nums[n] = -1;
		fixDown(nums,0,n);
	}

	public void fixDown(int[] nums,int n,int heapsize) {
		int l = n*2+1;
		int r = n*2+2;
		int largest = n;

		if( l < heapsize && nums[l] > nums[largest]) {
			largest = l;
		}

		if( r < heapsize && nums[r] > nums[largest]) {
			largest = r;
		}

		if(largest != n) {
			int temp = nums[largest];
			nums[largest] = nums[n];
			nums[n] = temp;
			fixDown(nums,largest,heapsize);
		}
	}

	public void buildHeap(int[] nums) {
		for(int i=nums.length/2;i>=0;i--) {
			fixDown(nums,i,nums.length);
		}
	}
}